// 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

// 如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。

// 我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。

// 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。

//  

// 示例 1：


// 输入：root = [1,2,3,4], x = 4, y = 3
// 输出：false
// 示例 2：


// 输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
// 输出：true
// 示例 3：



// 输入：root = [1,2,3,null,4], x = 2, y = 3
// 输出：false
//  

// 提示：

// 二叉树的节点数介于 2 到 100 之间。
// 每个节点的值都是唯一的、范围为 1 到 100 的整数。
//  


// Definition for a binary tree node.

#include <queue>
#include <unordered_map>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution1 {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        if (root == NULL || root->val == x || root->val == y) {
            return false;
        }
        return dfs(root->left, x, y, 2, root->val) || dfs(root->right, x, y, 2, root->val);
    }
    bool dfs(TreeNode* root, int x, int y, int curDepth, int curParent) {
        if (root == NULL || (depth != 0 && curDepth > depth)) {
            return false;
        }
        if (root->val == x || root->val == y) {
            if (depth == 0) {
                depth = curDepth;
                parent = curParent;
                return false;
            } else {
                return depth == curDepth && parent != curParent;
            }
        }
        return dfs(root->left, x, y, curDepth + 1, root->val) || dfs(root->right, x, y, curDepth + 1, root->val);
    }
private:
    int depth{0}; // 父节点的深度
    int parent{0};
};

// 层序遍历，使用hash
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        unordered_map<int, int> Mdepth{}; // 每个值对应一个深度
        unordered_map<int, TreeNode*> Mroot{}; // 每个值对应一个父节点
        queue<TreeNode*> Q{};
        Q.push(root);
        int depth{0};
        while(!Q.empty()) {
            ++depth;
            int len = Q.size();
            for(int i = 0; i < len; i++) {
                TreeNode* node = Q.front();
                Q.pop();
                if(node->left) {
                    Q.push(node->left);
                    Mroot[node->left->val] = node;
                    Mdepth[node->left->val] = depth;
                }
                if(node->right) {
                    Q.push(node->right);
                    Mroot[node->right->val] = node;
                    Mdepth[node->right->val] = depth;
                }
            }
        }
        if(Mroot[x] != Mroot[y] && Mdepth[x] == Mdepth[y])
            return true;
        return false;
    }
};

#include "stdc++.h"
/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        if (root == nullptr || root->val == x || root->val == y) {
            return false;
        }

        int x_parentVal{0};
        int x_depth{-1};
        BFS(root, x, x_parentVal, x_depth);

        int y_parentVal{0};
        int y_depth{-1};
        BFS(root, y, y_parentVal, y_depth);

        return (x_depth == y_depth) && (x_parentVal != y_parentVal);
    }
    // 层序遍历
    void BFS(TreeNode* root, const int& targetVal, int& parentVal, int& depth) {
        if (root == nullptr) {
            return;
        }
        queue<TreeNode*> q{};
        q.push(root);
        while (!q.empty()) {
            depth += 1;
            int n = q.size();
            vector<TreeNode*> vec(n, nullptr);
            for (int i{0}; i < n; ++i) {
                TreeNode* node = q.front();
                q.pop();
                if (node->left) {
                    if (node->left->val == targetVal) {
                        parentVal = node->val;
                        return;
                    }
                    q.push(node->left);
                }
                if (node->right) {
                    if (node->right->val == targetVal) {
                        parentVal = node->val;
                        return;
                    }
                    q.push(node->right);
                }
                vec[i] = node;
            }
        }
        return;
    }
};

// 层序遍历，只需要一轮遍历
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        if (root == nullptr || root->val == x || root->val == y) {
            return false;
        }
        int x_parent{0};
        int y_parent{0};

        queue<TreeNode*> q{};
        q.push(root);
        while (!q.empty()) {
            int n = q.size();
            vector<TreeNode*> vec(n, nullptr);
            for (int i{0}; i < n; ++i) {
                TreeNode* node = q.front();
                q.pop();
                vec[i] = node;
                if (node->left) {
                    if (node->left->val == x) {
                        x_parent = node->val;
                    } else if (node->left->val == y) {
                        y_parent = node->val;
                    }
                    q.push(node->left);
                }
                if (node->right) {
                    if (node->right->val == x) {
                        x_parent = node->val;
                    } else if (node->right->val == y) {
                        y_parent = node->val;
                    }
                    q.push(node->right);
                }
            }
            // 不在同一层
            if ((x_parent == 0 && y_parent != 0) || (x_parent != 0 && y_parent == 0)) {
                return false;
            }
            // 在同一层并且父节点不一样
            if (x_parent != y_parent) {
                return true;
            }
        }
        return false;
    }
};